Google Maps API Design Evaluation and Latency Budget

Learn how we meet the non-functional requirements and estimate the response time of the Google Maps APIs.

Introduction#

We've discussed the design considerations and API model for each functional requirement. In this lesson, we'll cover the approaches for achieving our non-functional requirements and estimate the response time of our Google Maps services.

Non-functional requirements#

Let's discuss how we achieve the non-functional requirements for our APIs one by one.

Availability#

We ensure the availability of our service by replicating our Google Maps services (such as maps, route finder, and places). For example, if a service is not available in one region, the API gateway can route the request to the available replica of this service in another region. Furthermore, if the server is not compatible with the WebSocket while upgrading, we fall back to HTTP/2. It is a trade-off between availability and low latency, but low latency is bearable when it is instead of unavailability of the service.

We improve availability by making the client intelligent. For example, if somehow a WebSocket connection is lost with the navigation service, the client updates the location of the client on the map locally. Once the connection is stable, we update the remaining distance and time on the client side. Moreover, storing maps on the client side can also improve the user-perceived latency.

Accuracy #

The accuracy of the results depends on the accuracy of the client's location, so the GPS should be turned on while using the Google Maps service. It also depends on the backend algorithms (such as Dijkstra's and A* algorithms) of the route-finding service to find the optimal path. Apart from algorithms, technologies like machine learning (ML) play a vital role in finding the best routes. For example, if a frequently used route is suddenly avoided by Google Maps users, the service can intelligently guess that there is a temporary route closure and suggest alternate routes. Another critical factor that improves the accuracy of the service is crowd-sourced traffic information. The ETA is improved by performing analytics on the user's data and finding patterns to detect any anomaly on the routes and, subsequently, adjusting the ETA calculation.

Google Maps continuously updates and improves the maps using user feedback. The user can report errors in maps by reporting them. Google Maps also uses information from its frequent users to improve—it allows users to provide feedback on their experience and update diversions due to road construction or other reasons.

Scalability #

The stateless nature of the HTTP allows our service to scale easily. Because each request is independent, it’s easy for the API gateway to route the incoming requests to any available node. We also make effective use of architectural styles. For instance, we use WebSockets only during the navigation service because we can provide and scale other services conveniently using REST. Moreover, our API has dedicated services working in tandem with each other, still operating independently.

Low latency#

We use the appropriate connection types to obtain low latency for each type of service. For instance, we use WebSocket connections between the client and navigation, which overcomes overheads caused by HTTP/1.1. For the /maps endpoint, we ensure low latency by having regionally distributed CDNs and caching to quickly retrieve the map tiles and the frequently searched places. Furthermore, the neighboring tiles in the vicinity of the user's current location are prefetched, because the user is expected to scroll around the map. We also cache commonly used routes and use them to find new routes. For example, if the path from A to B has been cached, then for the path A->B->C, we use the cached path A->B and only need to find the shortest path from B to C.

Achieving Non-Functional Requirements

Non-Functional Requirements

Approaches


Availability

  • Improving user-perceived availability through client-side intelligence
  • Allowing clients to store maps and cache frequently used routes
  • Fallback to HTTP/2
  • Replicating Google Maps services


Accuracy

  • Using GPS to get more accurate results
  • Using intelligent backend algorithms to find most suitable routes
  • Performing analytics on the users’ locations

Scalability

  • Stateless communication between clients and services
  • Allowing versioning to scale services


Low latency

  • Regionally distributed Google Maps server
  • Caching frequently searched routes
  • WebSocket connection between client and navigation service
  • Prefetching neighboring map tiles

Latency budget#

In this section, we'll estimate the response time of our Google Maps API. The response time helps us to measure the performance of our API. We calculate and estimate the size of the request and response for each service. Afterward, we estimate the response time based on the request and response size.

As discussed in the back-of-the-envelope latency calculations, in the case of GET, the average RTTRTT remains the same regardless of the data size (due to the small request size), and the time to download the response varies by 0.4 ms0.4\ ms per KB.

Let's start with the maps service.

Maps service#

The maps service uses the GET request to get the links of the map tiles in a response. Let's estimate the request and response size required for the maps service.

  • Request size: The estimated request size is 1 KB, including the header and query parameters. The GET method has no body, so the request body size is zero.

  • Response size: Assuming that a map tile is roughly 25 KBs in size, the approximate response size for getting map tiles from the maps service, including the response header and body size, is 28 KBs.

We need to calculate latency and processing time to estimate the response time. Our back-of-the-envelope calculations precalculated the average minimum processing time (4 ms) and maximum processing time (69 ms) for interacting with other services to process a request. Remember that we don't assume the size of the request message during the latency and response time calculation of a GET request, because of the small size of the GET request message.

The following calculator calculates the latency and estimates the response time based on our request and response size for the map service.

Response Time Calculator for the Map Service

Enter the size in KBs28KB
Minimum latencyf201.7ms
Maximum latencyf282.7ms
Minimum response timef205.7ms
Maximum response timef351.7ms

Assuming the response size is 28 KBs, then the latency is calculated as follows:

Timelatency_min=Timebase_min+RTTget+0.4×size of response (KBs)=120.5+70+0.4×28=201.7 msTime_{latency\_min} = Time_{base\_min} + RTT_{get} + 0.4 \times size\ of\ response\ (KBs) = 120.5 + 70 + 0.4 \times 28 = 201.7\ ms

Timelatency_max=Timebase_max+RTTget+0.4×size of response (KBs)=201.5+70+0.4×28=282.7 msTime_{latency\_max} = Time_{base\_max} + RTT_{get} + 0.4 \times size\ of\ response\ (KBs) = 201.5 + 70 + 0.4 \times 28 = 282.7\ ms

Similarly, the response time is calculated using the following equation:

TimeResponse=Timelatency+TimeprocessingTime_{Response} = Time_{latency}+ Time_{processing}

Now, for minimum response time, we use minimum values of base time and processing time:

TimeResponse_min=Timelatency_min+Timeprocessing_min=201.7 ms+4 ms=205.7 msTime_{Response\_min} = Time_{latency\_min}+ Time_{processing\_min}= 201.7\ ms + 4\ ms = 205.7\ ms

Now, for maximum response time, we use maximum values of base time and processing time:

TimeResponse_max=Timelatency_max+Timeprocessing_max=282.7 ms+69 ms=351.7 msTime_{Response\_max} = Time_{latency\_max}+ Time_{processing\_max}= 282.7\ ms + 69\ ms = 351.7\ ms

A summary of the overall response time for the maps service is shown in the illustration below:

Latency and processing time of maps service
Latency and processing time of maps service

Route finder service#

An optimal path includes multiple factors such as ETA, distance, number of turns, and traffic conditions. The route finder service uses a GET request to get a path from the service. The response time for this service always varies depending on various factors, such as the number of steps or stops between the source and destination points.

Let's estimate the request and response size for this service:

  • Request size: The estimated request size is 1 KB, including the header and query parameters.

  • Response size: Assuming we're traveling from point A to point B without any stop, the approximate response size is 80 KB which includes the size of the header, query parameters, and body.

The following calculator calculates the latency and estimates the response time based on our request and response size for the route finder service.

Response Time Calculator for the Route Finder Service

Enter the size in KBs80KB
Minimum latencyf222.5ms
Maximum latencyf303.5ms
Minimum response timef226.5ms
Maximum response timef372.5ms

A summary of the overall response time for the route finder service is shown in the illustration below:

Latency and processing time of the router finder service
Latency and processing time of the router finder service

Note: The response time of various requests to interact with maps service is in the ideal range of 0.1–1s, which is adequate according to the low latency requirements.

The navigation requires a WebSocket connection first, and then the client can exchange data over this connection. An HTTP upgrade connection request to WebSocket happens only once, and it takes a maximum of 275.9 ms275.9\ ms to exchange a 1 KB header. The calculation details of the response time to upgrade the connection to WebSockets can be found here.

Let's calculate the response time between clients and the navigation service for sending and receiving events on a WebSocket connection. For example, sending a location from the client and receiving updates related to distance and time from the server side.

Message size#

The estimated size of sending the location to the navigation service is 500 bytes, which includes connection_id, source, and destination. In contrast, the estimated size of receiving the updates related to distance and time takes 700 bytes, which includes connection_id, transport_mode, duration, and distance.

Message sizeoutgoing=500 bytes0.48 KBMessage sizeincoming=700 bytes0.68 KBMessage\ size_{outgoing}= 500\ bytes \approx 0.48 \ KB \\Message\ size_{incoming}= 700\ bytes \approx 0.68 \ KB

Response time#

We only use the base propagation and download time here, because WebSockets do not follow the request-response model.

Response Time Calculator for the Navigation Service

Outgoing message size in KBs0.48KB
Incoming message size in KBs0.68KB
Outgoing message latencyf35.192ms
Incoming message latencyf35.272ms
User perceived responsef74.464ms

The following formula calculates the latency for sending and receiving events:

Latency=Base propagation delay+Message size×0.4Latency = Base\ propagation \ delay + Message\ size\times0.4

Latencyoutgoing=35+0.48×0.4=35.192 msLatency_{outgoing} = 35 + 0.48\times0.4= 35.192 \ ms

Latencyincoming=35+0.68×0.4=35.272 msLatency_{incoming} = 35 + 0.68\times0.4 = 35.272 \ ms

Similarly,

User perceived responsemin=Latencyoutgoing+Latencyincoming+ProcessingminUser\ perceived \ response_{min} = Latency_{outgoing} + Latency_{incoming} + Processing_{min}

User perceived response=35.192+35.272+4=74.464 msUser\ perceived \ response = 35.192 + 35.272 + 4 = 74.464\ ms

A summary of the overall response time for the navigation service is shown in the illustration below:

Latency and processing time of the navigation service
Latency and processing time of the navigation service

Note: A latency of 50–100 ms is considered adequate for real-time communication in a persistent connection. The response time for bidirectional communication between the client and the navigation service is ~ 75 ms75\ ms (an average response time), which is adequate.

Summary#

In this chapter, we learned how to design the API for a route finder and navigation application like Google Maps. We mainly discussed the involved components and their efficient communication in Google Maps. We also discussed how live updates are sent to different clients in real-time. The design decisions made for this problem can also be helpful for similar services, such as Yelp, Uber, Snapchat, and so on.

API Model for Google Maps Service

Requirements of the Zoom API